šŸ“ Edit Distance for Document Transformation

Help Alex minimize the cost to transform one document into another

šŸ‘©ā€šŸ’» Alex's Document Transformation Challenge

šŸŽÆ The Mission:

Help Alex find the minimum cost to transform one document (doc1) into another (doc2) using insertion (cost 3), deletion (cost 2), or substitution (cost 5).

šŸ“‹ Requirements:

  • Transform doc1 into doc2 with minimum cost
  • Handle strings of length 1 to 100
  • Output a single integer: the minimum cost

Input/Output Specifications

  • Input: String doc1 (original), String doc2 (target)
  • Output: Single integer (minimum cost)

Example: doc1 = "cat", doc2 = "rat"

doc1:

c
a
t

doc2:

r
a
t

Output: 5 (substitute cā†’r)

Example: doc1 = "hello", doc2 = "world"

doc1:

h
e
l
l
o

doc2:

w
o
r
l
d

Output: 20 (multiple operations)

āš” Edit Distance Explained

How Edit Distance Works

  1. Dynamic Programming: Use a DP table where dp[i][j] is the minimum cost to transform first i characters of doc1 into first j characters of doc2
  2. Base Cases: Initialize dp[i][0] = i * deleteCost, dp[0][j] = j * insertCost
  3. Fill Table: For each (i,j), choose minimum of deletion, insertion, or substitution (if characters differ)

DP Table Example (doc1 = "ca", doc2 = "ra")

\ 0ra
0036
c256
a475

Cost: 5 (substitute cā†’r)

Time Complexity

O(n * m)

For filling the DP table (n, m are string lengths)

Space Complexity

O(n * m)

For the DP table

Why Edit Distance?

  • āœ… Minimizes cost of string transformations
  • āœ… Handles insertion, deletion, substitution
  • āœ… Useful in text editing, spell checkers
  • āŒ Space-intensive for long strings

šŸ” Step-by-Step Edit Distance Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input strings
2. Initialize DP table
3. Fill DP table
4. Display result

Current Strings:

doc1:

doc2:

DP Table:

šŸŽ® Practice Edit Distance

Enter strings, then click "Compute Cost"

Test Cases

Example 1: doc1 = "cat", doc2 = "rat" ā†’ 5

Example 2: doc1 = "hello", doc2 = "world" ā†’ 20

šŸ“Š Algorithm Analysis

Edit Distance Process

  1. Initialize DP: Set dp[i][0] = i * 2 (deletions), dp[0][j] = j * 3 (insertions)
  2. Fill DP Table: For each (i,j), if characters match, copy dp[i-1][j-1]; else, take min of deletion (2), insertion (3), substitution (5)
  3. Output: Print dp[n][m] (minimum cost)

Time Complexity

O(n * m)

For filling the DP table

Space Complexity

O(n * m)

For the DP table

Key Points

  • Dynamic Programming: Optimizes transformation cost
  • Operations: Insertion (3), Deletion (2), Substitution (5)
  • Applications: Text editing, spell checkers, bioinformatics
  • Limitation: Space-intensive for long strings